package com.twq.collection.framework.seq

import scala.annotation.tailrec
import scala.collection.LinearSeq

/**
 * Created by tangweiqun on 2017/11/15.
 * Seq是一个有长度且其元素都有一个固定的下标值(从0开始)的Iterable
 */
object SeqTest {
  def main(args: Array[String]): Unit = {
    //1、trait Seq是通过length和apply两个接口方法定义的，代表连续有序(有序并不代表排序sorted)的集合
    //apply是根据序号进行索引操作，而length则是返回集合的大小
    //Seq不对索引或者length做任何的性能保证，仅用来将有序集合和Set/Map区分开
    //也就是说，如果元素插入集合的顺序是重要的，并且允许重复元素，那么就使用Seq
    //比如：记录采用的音频数据，其记录的顺序对于数据的处理是非常重要的
    val x = Seq(2, 1, 30, -2, 20, 1, 2, 1)
    x.tails map (_.take(2)) filter (_.length > 1) map (_.sum) toList
    //res4: List[Int] = List(3, 31, 28, 18, 21, 3, 2)

    //效果和上面是一样的，我们推荐使用sliding，而不是tails
    x.sliding(2).map(_.sum).toList
    //res4: List[Int] = List(3, 31, 28, 18, 21, 3, 2)

    //2、所有的方法
    val seq = Seq(1, 2, 4, 2, 1, 1) //Seq的默认实现是不可变集合List
    //Indexing and Length
    seq(2)
    seq.apply(2)
    seq.isDefinedAt(4)
    seq.length
    seq.lengthCompare(4) //如果seq的长度比4小则返回-1，长度比4大则返回1，否则返回0
    seq.indices

    //Index Search
    seq.indexOf(3)
    seq.lastIndexOf(1)
    seq.indexOfSlice(Seq(2, 1), 2) //从seq的下标为2的位置开始，返回Seq(2, 1)在seq中的位置
    seq.lastIndexOfSlice(Seq(2, 1), 2) //到2为止
    seq.indexWhere(_ == 1, 2) //从seq的下标为2的位置开始,返回符合条件的下标
    seq.segmentLength(_ == 1, 2) //从seq的下标为2的位置开始,返回连续符合条件的元素的个数，如果碰到不符合条件的元素则直接返回
    seq.prefixLength(_ == 1) //返回连续符合条件的元素的个数，如果碰到不符合条件的元素则直接返回

    //Additions
    3 +: seq
    seq :+ 3
    seq.padTo(10, 3)

    //Updates
    seq.patch(2, Seq(88, 99), 3) //从seq的下标2开始将seq长度为3的元素集合替换为Seq(88, 99)
    seq.updated(2, 100)

    //Sorting
    seq.sorted
    seq.sortWith(_ < _)
    seq.sortBy(_ % 2)
    val person = Seq(People("kk", 23), People("mm", 21), People("mssm", 81))
    implicit object PersonOrdering extends Ordering[People] {
      override def compare(x: People, y: People): Int = x.age - y.age
    }
    person.sorted

    //Reversals
    seq.reverse
    seq.reverseIterator //和seq.reverse.iterator一样，但是会更加的高效
    seq.reverseMap(_ + 3)

    //Comparisons
    val ys = Seq(2, 3, 1, 1)
    seq.startsWith(ys, 2)
    seq.endsWith(ys)
    seq.contains(3)
    seq.containsSlice(ys)
    (seq.corresponds(ys)) ((x, y) => x + y == 4) //判断两个序列的元素对应起来是否符合条件

    //Multiset Operations
    seq.intersect(ys)
    seq.diff(ys)
    seq.union(ys)
    seq.distinct

    //3、trait LinearSeq表示能够分割为头元素 + 尾集合的集合，是Seq的子类
    //定义了三个方法：isEmpty(集合是否非空)、head(非空集合的第一个元素)
    // 和tail(去掉第一个元素剩下的所有元素的集合)
    //这种集合类型通过头元素分割集合的尾递归算法非常的理想
    val linearSeq = LinearSeq(1, 2, 3)
    linearSeq.head
    linearSeq.tail
    linearSeq.isEmpty
    val tree = Branch(1, Leaf(2), Branch(3, Leaf(4), NilTree))
    traverse(tree)(println)
    //当需要把一个普通递归的算法转化成尾递归或者循环算法时，
    // 在堆(heap)上手工创建一个栈(stack)，然后用这个栈来完成实际功能是一种常见的做法
    //在使用函数式风格的尾递归算法时，LinearSeq是一个恰当的选择

    //List是常用的LinearSeq的实现集合

    //4、IndexedSeq也是Seq的子类，它在随机访问的时候更为高效
    val indexedSeq = IndexedSeq(1, 2, 3) //默认情况下是创建一个不可变的Vector
    indexedSeq.updated(1, 5) //将集合中下标为1的值改成5，生成一个新的集合
    //访问IndexedSeq
    indexedSeq.apply(1)
    indexedSeq(2)

    //Array和ArrayBuffer是常用的IndexedSeq的实现集合

    //Vector同时支持高效的线形访问和随机访问，如果场景需要线形访问和随机访问的话，则用Vector

    //5、LinearSeq和IndexedSeq都包含可变和不可变的
    val immutableLinearSeq = scala.collection.immutable.LinearSeq(1, 2, 3)
    val mutableLinearSeq = scala.collection.mutable.LinearSeq(1, 2, 3)

    val immutableIndexedSeq = scala.collection.immutable.IndexedSeq(1, 2, 3)
    val mutableIndexedSeq = scala.collection.mutable.IndexedSeq(1, 2, 3)

    //可变和不可变都有updated方法，都是返回一个新的Seq集合
    immutableIndexedSeq.updated(1, 5)
    mutableIndexedSeq.updated(1, 5)

    //update只有是可变集合有，改变原集合，不产生新的集合
    mutableIndexedSeq.update(1, 5)
    //immutableIndexedSeq.update(1, 5) 不存在的方法
  }

  def traverse[A, U](t: BinaryTree[A])(f: A => U): Unit = {

    @tailrec
    def traverseHelper(current: BinaryTree[A],
                       next: LinearSeq[BinaryTree[A]]): Unit = {
      current match {
        case Branch(value, lhs, rhs) =>
          f(value)
          traverseHelper(lhs, rhs +: next)
        case Leaf(value) if !next.isEmpty =>
          f(value)
          traverseHelper(next.head, next.tail)
        case Leaf(value) =>
          f(value)
        case NilTree if !next.isEmpty =>
          traverseHelper(next.head, next.tail)
        case NilTree => ()

      }
    }

    traverseHelper(t, LinearSeq())
  }
}


sealed trait BinaryTree[+A]

case object NilTree extends BinaryTree[Nothing]

case class Branch[+A](value: A,
                      lhs: BinaryTree[A],
                      rhs: BinaryTree[A]) extends BinaryTree[A]

case class Leaf[+A](value: A) extends BinaryTree[A]

case class People(name: String, age: Int)